Всех приветствую. Сегодня мы разберем несколько интересных задач, которые запросто могут вам попасться на собеседованиях в таких фирмах, как Яндекс, Сбер, Тинькофф и другие. Сразу предупрежу, на платформе Leetcode эти задачи оценивались бы как Medium сложности, однако сложного тут ничего нет. Каждую из них с небольшой подготовкой может решить каждый.
Первую задачу я разберу максимально подробно, однако остальные задачи вам придется разбирать самостоятельно. Их разборы вы можете найти на ютубе яндекс - разборов. Интересно? Тогда вам по ссылкам ниже:
Ладно, так уж и быть, расскажу я вам, каким образом именно нужно мыслить, когда вы решаете задачи (мое субъективное мнение).
Давайте рассмотрим одну из задач, которая однажды мне НЕ попалась на собесе в Яндекс. (СОВЕРшЕННО СЛУЧАЙНАЯ ЗАДАЧА НЕ С ЯНДЕКСА)
На вход подается массив, состоящий только из чисел. Вам необходимо вывести строку, которая перечислит через запятую все диапазоны чисел, причем в порядке возрастания.
Пример:
[1,0,2,3,5] -> "0-3,5"
[3,6,5,4,9,8,0] -> "0,3-6,8-9"
[3,2] ->"2,3"
Для начала давайте откопаем простые находки, которые помогут на в решении задачи.
Если начать копаться, то можно обратить внимание на формат ответа, который нас интересует. Так как на выходе нас просят строку, то ответ задачи - строка. Если же на вход нам дают не строку, а список, то, скорее всего, мы должны будем как-то преобразовать список в строку. Как раз для такого случая существует метод .join(), который способен объединить все элементы списка в строку, используя конкретный разделитель.
Давайте вспомним, как он работает:
names=['Сережа','Вася','Петя','Коля']
print("; ".join(names)) # -> "Сережа; Вася; Петя; Коля"
Вернемся к нашей задаче.
От нас требуют вид ответа "0,3-6,8-9", значит мы можем сначала создать список, для данного примера вида ['0',"3-6","8-9"], а потом использовать метод ",".join(['0',"3-6","8-9"]), то есть разделим такие строки в списке между собой с помощью запятых.
Теперь используем то, что уже имеем, а именно:
['0',"3-6","8-9"]Заметим, что в этом списке все числа как бы отсортированы, а значит нам для начала придется, хотим мы этого или нет, отсортировать начальный список.
Дело в том, что если мы хотим создать такой список быстро, то мы будем просто .append-ить в список данные строки. То есть сначала ноль, потом диапазон 3-6, потом 8-9. А это в свою очередь значит, что мы сначала должны будем найти 0, потом числа больше 0, и так далее. Всё это намекает на отсортированный список
Думаю, всем нам ясно, что сортировать начальный список мы будем не в конце программы, а в ее начале, потому что нам нужно сразу же избавиться от этой проблемы. Можно сортировать по разному, в нашем случае это встроенная функция sorted()
На самом деле это самая главная ошибка любого новичка - НЕ оценивать сложность своего решения.
Впервые с этой проблемой столкнулись в 20 веке, когда мощности машин были на ничтожном уровне. Скорости у машин были маленькие, и необходимо было максимально оптимизировать свой код. И именно тогда обнаружили в таких небольших задачах как наша, что при определенных ситуациях она начинает тратить слишком много времени. Всё дело в том, что если задача имеет, к примеру, сложность O(N^2) (Обычно это происходит когда каждый элемент массива проверяется с каждым другим элементом массива. Если в массиве 100 элементов, то каждый будет сверяться с каждым, что даст нам 100*100=10000 операций. Про остальное можете прочитать сами)
Хорошо, но как нам понять, какая сложность нам нужна?
Отлично! У нас уже появился начальный каркас решения задачи. Давайте его запишем.
def arr_range(arr:list[int]) -> str: # На вход дают лист из чисел, на выходе строку
q=sorted(arr) # Отсортировали список
ans=[] # В этот список будем записывать все наши строки
# Должен быть return ','.join(ans)
ansdef arr_range(arr:list[int]) -> str: # На вход дают лист из чисел, на выходе строку
q=sorted(arr) # Отсортировали список
ans=[] # В этот список будем записывать все наши строки
if len(q)==0:
return ""
if len(q)==1:
return q[0]
start=0
last=start
for i in range(len(q)-1):
a=q[i]
b=q[i+1]
if b-a==1:
last+=1
if i==len(q)-2:
ans.append(f"{q[start]}-{q[last]}")
else:
if start==last:
ans.append(str(a))
else:
ans.append(f"{q[start]}-{q[last]}")
start=i+1
last=start
if i==len(q)-2:
ans.append(str(b))
return ','.join(ans)
print(arr_range([0,1,2,5,3,7,6,9]))
print(arr_range([0,1]))
print(arr_range([0,2]))
print(arr_range([1,2,3,4,7,8,10,11]))
print(arr_range([]))
На выходе получаем нужные результаты:
0-3,5-7,9
0-1
0,2
1-4,7-8,10-11
<-тип пустая строка
На вход дается строка. Выведите самый длинный палиндром, который в расположен в данной строке.
Ниже привожу два различных решения (одно длинное, другое короткое из-за использования особенностей некоторых функций)
def long_palindrom(self,s:str)->str:
def palindromer(s,x,y):
# print(x,y,end=' ')
if x < 0 or y>len(s)-1:
return s[x+1:y],y-x-1
if s[x]==s[y]:
if x == 0 or y==len(s)-1:
# print(s[x:y+1],y-x+1,"Дошли до конца",type(s),type(y-x+1))
return s[x:y+1],y-x+1
# print('идем дальше',s[x:y+1],x,y)
x-=1
y+=1
p,t=palindromer(s,x,y)
return p,t
else:
# print(s[x+1:y],y-x-1,"Не совпадает,",type(s),type(y-x+1))
return s[x+1:y],y-x-1
q=s.lower()
del_s=",. "
for letter in del_s:
q=q.replace(letter,'')
if len(q)==1:
return q
max_arr=[]
max_len=0
for i in range(0,len(q)):
arr,cur_len=palindromer(q,i-1,i+1)
if cur_len>=max_len:
max_len=cur_len
max_arr=arr
for i in range(1,len(q)):
arr,cur_len=palindromer(q,i-1,i)
if cur_len>=max_len:
max_len=cur_len
max_arr=arr
return max_arr
def long_palindrom_2(self, s: str) -> str:
def palindromer(l,r):
while (l>=0) and (r<n) and (s[l]==s[r]):
l-=1
r+=1
return s[l+1:r]
max_arr = ""
for i in range(len(s)):
max_arr = max(max_arr, palindromer(i,i), palindromer(i, i+1), key=lambda x: len(x)) # Нахождение самого длинного палиндрома
return max_arr
Есть некая строка s, состоящая из различных символов
Найти максимально длинную подстроку, состоящую из уникальных симоволов, т.е. без повторений
class Solution:
def understr(self, a: str) -> str:
temp=[]
maxy=[]
n_maxy=0
n=0
for letter in a:
if letter not in temp:
temp.append(letter)
n+=1
else:
if n>=n_maxy:
maxy=temp
n_maxy=n
n=0
temp=[letter]
return ''.join(maxy)
(Из литкода easy задача чисто ради решения нового посмотреть)
Ссылка на задачу: Перейти
The Two Sum problem asks us to find two numbers in an array that sum up to a given target value. We need to return the indices of these two numbers.
Approach using a hash table:
This approach has a time complexity of O(n) since hash table lookups take constant time on average. It allows us to solve the Two Sum problem efficiently by making just one pass through the array.
Интуиция
Задача о двух суммах требует от нас найти в массиве два числа, сумма которых равна заданному целевому значению. Нам нужно вернуть индексы этих двух чисел.
Подход
Один из подходов грубой силы заключается в рассмотрении каждой пары элементов и проверке, равна ли их сумма целевому значению. Это можно сделать с помощью вложенных циклов, где внешний цикл выполняет итерацию от первого элемента к предпоследнему элементу, а внутренний цикл выполняет итерацию от следующего элемента к последнему элементу. Однако этот подход имеет временную сложность O (n ^ 2).
Более эффективным подходом является использование хэш-таблицы (unordered_map в C++). Мы можем выполнить итерацию по массиву один раз и для каждого элемента проверить, существует ли целевой минус текущий элемент в хэш-таблице. Если это так, то мы нашли правильную пару чисел. Если нет, мы добавляем текущий элемент в хэш-таблицу.
Подход с использованием хэш-таблицы:
Создайте пустую хэш-таблицу для хранения элементов и их индексов.
Выполните итерацию по массиву слева направо.
Для каждого элемента nums[i] вычислите дополнение, вычитая его из целевого значения: дополнение = целевое значение - nums[i].
Проверьте, существует ли дополнение в хэш-таблице. Если это так, то мы нашли решение.
Если дополнение не существует в хэш-таблице, добавьте текущий элемент nums[i] в хэш-таблицу с его индексом в качестве значения.
Повторяйте шаги 3-5, пока мы не найдем решение или не дойдем до конца массива.
Если решение не найдено, верните пустой массив или соответствующий индикатор.
Этот подход имеет временную сложность O (n), поскольку поиск по хэш-таблице в среднем занимает постоянное время. Это позволяет нам эффективно решить задачу о двух суммах, выполнив всего один проход по массиву.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return [] # No solution found
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numMap = {}
n = len(nums)
# Build the hash table
for i in range(n):
numMap[nums[i]] = i
# Find the complement
for i in range(n):
complement = target - nums[i]
if complement in numMap and numMap[complement] != i:
return [i, numMap[complement]]
return [] # No solution found
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
numMap = {}
n = len(nums)
for i in range(n):
complement = target - nums[i]
if complement in numMap:
return [numMap[complement], i]
numMap[nums[i]] = i
return [] # No solution found